// var wordBreak = function(s, wordDict) {
//   // dp[i] 表示s(0,i-1)能在词典中查找到
//   let dp = new Array(s.length).fill([])
//   for(var i = 1;i<=s.length;i++) {
//       for(var j = 0;j<=i;j++) {
//           if(dp[j]&&wordDict.includes(s.slice(j,i))) {
//               // if(dp[i].length) {
//               // }else {
//                 dp[i] = [...dp[j],s.slice(j,i)]
//                 console.log(dp[i]);
//               // }
//           }
//       }
//   }
//   // console.log(dp);
// };
const backtrack = (s, length, wordSet, index, map) => {
  // "catsanddog"
  if (map.has(index)) {
    return map.get(index);
  }
  const wordBreaks = [];
  if (index === length) {
    wordBreaks.push([]);
  }
  for (let i = index + 1; i <= length; i++) {
    const word = s.substring(index, i);
    if (wordSet.has(word)) {
      const nextWordBreaks = backtrack(s, length, wordSet, i, map);
      for (const nextWordBreak of nextWordBreaks) {
        const wordBreak = [word, ...nextWordBreak]
        wordBreaks.push(wordBreak);
      }
    }
  }
  map.set(index, wordBreaks);
  return wordBreaks;
}
var wordBreak = function (s, wordDict) {
  const map = new Map();
  const wordBreaks = backtrack(s, s.length, new Set(wordDict), 0, map);
  const breakList = [];
  for (const wordBreak of wordBreaks) {
    breakList.push(wordBreak.join(' '));
  }
  return breakList;
};


let s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]
wordBreak(s, wordDict)
